package com.LeeCode;

/**
 * 统计隐藏数组数目
 */

public class Code2145 {
    public static void main(String[] args) {
        int[] nums = {3, -4, 5, 1, -2};
        int lower = -4, upper = 5;
        System.out.println(new Code2145().numberOfArrays1(nums, lower, upper));

    }

    public int numberOfArrays(int[] differences, int lower, int upper) {
        int ans = 0, upBound = Integer.MIN_VALUE, lowBound = Integer.MAX_VALUE, sum = 0;
        for (int nums : differences) {
            sum += nums;
            if (sum > upBound) {
                upBound = sum;
            }
            if (sum < lowBound) {
                lowBound = sum;
            }
        }
        for (int i = lower; i <= upper; i++) {
            if ((i + upBound) <= upper && (i + lowBound) >= lower) {
                ans++;
                System.out.println(i);
            }
        }
        return ans;
    }

    public int numberOfArrays1(int[] differences, int lower, int upper) {
        long minPrefixSum = 0, maxPrefixSum = 0, prefixSum = 0;
        for (int diff : differences) {
            prefixSum += diff;
            if (prefixSum > maxPrefixSum) {
                maxPrefixSum = prefixSum;
            }
            if (prefixSum < minPrefixSum) {
                minPrefixSum = prefixSum;
            }
        }
        // hidden[0] 必须满足：
        // 1. hidden[0] >= lower
        // 2. hidden[0] <= upper
        // 3. hidden[0] + minPrefixSum >= lower => hidden[0] >= lower - minPrefixSum
        // 4. hidden[0] + maxPrefixSum <= upper => hidden[0] <= upper - maxPrefixSum
        long left = Math.max(lower, lower - minPrefixSum);
        long right = Math.min(upper, upper - maxPrefixSum);
        if (left > right) {
            return 0;
        }
        return (int) (right - left + 1);
    }
}
